package leetcode_core.leetcode_5;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月09日 22:23
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int idx = 0;
        List<List<Integer>> list = new ArrayList<>();
        while (!q.isEmpty()){
            int size = q.size();
            System.out.println(size);
            list.add(new LinkedList<>());
            for(int i = 0;i<size;i++){
                TreeNode head = q.peek();
                //手动实现addLast和addFirst
                if(idx % 2 == 0){
                    list.get(idx).add(0,head.val);
                }else{
                    list.get(idx).add(i,head.val);
                }
                if(head.left != null){
                    q.offer(head.left);
                }
                if(head.right != null){
                    q.offer(head.right);
                }
            }
            idx++;
        }
        return list;
    }
}
